import java.util.Random;

public class FindKthLargest {
    /**
     *给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
     * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
     * @param nums
     * @param k
     * @return
     */
    Random random = new Random();
    public int findKthLargest(int[] nums, int k) {

        return quickList(nums,0,nums.length-1,nums.length-k);

    }

    public int quickList(int[] arr,int left,int right,int index){
        int q = randomPartition(arr,left,right);
        if (q==index){
            return arr[q];
        }else {
            return q<index?quickList(arr,q+1,right,index):quickList(arr,left,q-1,index);
        }
    }

    public int randomPartition(int[] arr,int left,int right){
        int i= random.nextInt(right-left+1)+1;
        swap(arr,i,right);
        return partition(arr,left,right);
    }

    public int partition(int[] arr,int left,int right){
       int x = arr[right],i = left-1;
       for (int j=1;j<right;j++){
           if (arr[j]<=x){
               swap(arr,++i,j);
           }
       }
       swap(arr,i+1,right);
       return i+1;
    }

    public void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
